2218. Coins

There are n coins on the table. Some of them are heads-up, while others are tails-up. Determine the minimum number of coins that need to be flipped so that all the coins end up facing the same side up.

Input. The first line contains the number of coins n (1 ≤ n ≤ 100). Each of the following n lines contains an integer: 1 if the coin is heads-up, and 0 if it is tails-up.

Output. Print the minimum number of coins that need to be flipped.

Sample input	Sample output
5 1 0 1 1 0	2

SOLUTION

mathematics

Algorithm analysis

Let’s find the sum of n input integers – this is the number of coins that are heads-up. Let this sum be denoted as s. To make all the coins heads-up, you need to flip the remaining n – s coins. To make all the coins tails-up, you need to flip s coins that are currently heads-up. Thus, the answer is min(s, n – s).

Example

There are s = 3 coins heads-up.

To make all the coins heads-up, you need to flip n – s = 5 – 3 = 2 coins. To make all the coins tails-up, you need to flip s = 3 coins. The answer to the problem is min(s, n – s) = min(3, 2) = 2 coins.

Algorithm realization

Read the input data. Compute the sum of n integers in the variable s.

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&v);

s += v;

}

Compute and print the result – the value of min(s, n – s).

if (s < n - s) printf("%d\n",s);

else printf("%d\n",n - s);